package com.lwl.Algorithmic_data_structure.class12二叉树;

import com.lwl.Utils.MyTreeNode;

/**
 * @author lwl
 * @Description 求最大的搜索二叉子树，自己可能不是二叉树，但是子节点有可能存在
 * @date 2023/6/1 8:44
 */
public class Code05getMaxSubBST {

    class Info {

        int min;

        int max;

        boolean isBST;

        int maxBSTSize;

        public Info(int min, int max, boolean isBST, int maxBSTSize) {
            this.min = min;
            this.max = max;
            this.isBST = isBST;
            this.maxBSTSize = maxBSTSize;
        }
    }

    public Info getMaxSubBST(MyTreeNode treeNode) {
        if (treeNode == null) {
            return new Info(Integer.MAX_VALUE, Integer.MIN_VALUE, true, 0);
        }
        // 这里都需要考虑左右信息，以及左右为空的情况

        Info leftInfo = getMaxSubBST(treeNode.left);
        Info rightInfo = getMaxSubBST(treeNode.right);
        boolean isBST = true;
        if (!leftInfo.isBST || !rightInfo.isBST || treeNode.value <= leftInfo.max || treeNode.value >= rightInfo.min) {
            isBST = false;
        }
        int min = Math.min(Math.min(leftInfo.min, rightInfo.min), treeNode.value);
        int max = Math.max(Math.max(leftInfo.max, rightInfo.max), treeNode.value);
        int maxBSTSize = Math.max(Math.max(leftInfo.maxBSTSize, rightInfo.maxBSTSize), 1);
        if (isBST) {
            maxBSTSize = leftInfo.maxBSTSize + rightInfo.maxBSTSize + 1;
        }
        return new Info(min, max, isBST, maxBSTSize);
    }

}
